jdk1.7与jdk1.8中HashMap区别（面试最详细版） |
您所在的位置：网站首页 › gt 2000 7和gt 2000 8什么区别 › jdk1.7与jdk1.8中HashMap区别（面试最详细版） |
|
一、区别
1. 最重要的一点是底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构; 2. jdk1.7中当哈希表为空时，会先调用inflateTable()初始化一个数组；而1.8则是直接调用resize()扩容; 3. 插入键值对的put方法的区别，1.8中会将节点插入到链表尾部，而1.7中是采用头插； 4. jdk1.7中的hash函数对哈希值的计算直接使用key的hashCode值，而1.8中则是采用key的hashCode异或上key的hashCode进行无符号右移16位的结果，避免了只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，使元素分布更均匀； 5. 扩容时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序；而且1.8是在元素插入后检测是否需要扩容，1.7则是在元素插入前； 6. jdk1.8是扩容时通过hash&cap==0将链表分散，无需改变hash值，而1.7是通过更新hashSeed来修改hash值达到分散的目的； 7. 扩容策略：1.7中是只要不小于阈值就直接扩容2倍；而1.8的扩容策略会更优化，当数组容量未达到64时，以2倍进行扩容，超过64之后若桶中元素个数不小于7就将链表转换为红黑树，但如果红黑树中的元素个数小于6就会还原为链表，当红黑树中元素不小于32的时候才会再次扩容。 二、JDK1.8 HashMap源码解读 1.桶的树形化 treeifyBin()(1)根据哈希表容量以及元素个数确定是扩容还是树形化； (2)如果是树形化则遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系； (3)让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容； //将桶内所有的 链表节点 替换成 红黑树节点 1 final void treeifyBin(Node[] tab, int hash) { 2 int n, index; Node e; 3 //如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容 4 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 5 resize(); 6 else if ((e = tab[index = (n - 1) & hash]) != null) { 7 //如果哈希表中的元素个数超过了 树形化阈值，进行树形化 8 // e 是哈希表中指定位置桶里的链表节点，从第一个开始 9 TreeNode hd = null, tl = null; //红黑树的头、尾节点 10 do { 11 //新建一个树形节点，内容和当前链表节点 e 一致 12 TreeNode p = replacementTreeNode(e, null); 13 if (tl == null) //确定树头节点 14 hd = p; 15 else { 16 p.prev = tl; 17 tl.next = p; 18 } 19 tl = p; 20 } while ((e = e.next) != null); 21 //让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了 22 if ((tab[index] = hd) != null) 23 hd.treeify(tab); 24 } 25 } 26 TreeNode replacementTreeNode(Node p, Node next) { 27 return new TreeNode(p.hash, p.key, p.value, next); 28 } 2.put()①.判断键值对数组table[i]是否为空，否则执行resize()扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④； ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table[i]，判断链表长度是否不小于7，不小于7就把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量是否超过阈值，如果超过了就进行扩容； 1 public V put(K key, V value) { 2 // 对key的hashCode()做hash 3 return putVal(hash(key), key, value, false, true); 4 } 5 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 7 boolean evict) { 8 Node[] tab; Node p; int n, i; 9 // 步骤①：tab为空则创建 10 if ((tab = table) == null || (n = tab.length) == 0) 11 n = (tab = resize()).length; 12 // 步骤②：计算index，并对null做处理 13 if ((p = tab[i = (n - 1) & hash]) == null) 14 tab[i] = newNode(hash, key, value, null); 15 else { 16 Node e; K k; 17 // 步骤③：节点key存在，直接覆盖value 18 if (p.hash == hash && 19 ((k = p.key) == key || (key != null && key.equals(k)))) 20 e = p; 21 // 步骤④：判断该链为红黑树 22 else if (p instanceof TreeNode) 23 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 24 // 步骤⑤：该链为链表 25 else { 26 for (int binCount = 0; ; ++binCount) { 27 if ((e = p.next) == null) { 28 p.next = newNode(hash, key,value,null); //链表长度大于8转换为红黑树进行处理 29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 30 treeifyBin(tab, hash); 31 break; 32 } // key已经存在直接覆盖value 33 if (e.hash == hash && 34 ((k = e.key) == key || (key != null && key.equals(k)))) 35 break; 36 p = e; 37 } 38 } 39 40 if (e != null) { // existing mapping for key 41 V oldValue = e.value; 42 if (!onlyIfAbsent || oldValue == null) 43 e.value = value; 44 afterNodeAccess(e); 45 return oldValue; 46 } 47 } 48 ++modCount; 49 // 步骤⑥：超过最大容量就扩容 50 if (++size > threshold) 51 resize(); 52 afterNodeInsertion(evict); 53 return null; 54 } 3.红黑树中查找元素 getTreeNode()(1) HashMap的查找方法是get(),它通过计算指定key的哈希值后，调用内部方法 getNode()； (2) getNode()方法中根据哈希表元素个数与哈希值计算出对应索引位置，找到key所在的桶的头结点，如果头节点恰好是红黑树节点，就调用红黑树节点的getTreeNode()方法，否则就遍历链表节点； (3) getTreeNode()方法通过调用红黑树的find()方法进行查找即可； (4) 由于之前添加时已经保证整个树是有序的，因此查找时基本就是折半查找，效率很高； 1 final Node getNode(int hash, Object key) { 2 Node[] tab; Node first, e; int n; K k; 3 if ((tab = table) != null && (n = tab.length) > 0 && 4 (first = tab[(n - 1) & hash]) != null) { 5 if (first.hash == hash && // always check first node 6 ((k = first.key) == key || (key != null && key.equals(k)))) 7 return first; 8 if ((e = first.next) != null) { 9 if (first instanceof TreeNode) 10 return ((TreeNode)first).getTreeNode(hash, key); 11 do { 12 if (e.hash == hash && 13 ((k = e.key) == key || (key != null && key.equals(k)))) 14 return e; 15 } while ((e = e.next) != null); 16 } 17 } 18 return null; 19 } 20 21 final TreeNode getTreeNode(int h, Object k) { 22 return ((parent != null) ? root() : this).find(h, k, null); 23 }
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |